\chapter{Вопрос № 29}

Количество перестановок как количество разбиений n -элементного множества на блоки с последующим циклическим упорядочиванием элементов в каждом блоке. Числа Стирлинга первого рода как количество разбиений n -элементного множества ровно на k блоков с последующим циклическим упорядочиванием элементов в каждом блоке.

\section{Перестановки через разбиения}

Задача разбить $n$-множество на блоки, затем каждый блок циклически упорядочить. Известно, что циклически упорядочить блок из $n$ элементов можно $\left(n-1\right)!$ способами, т. е. имеется производящая функция:
\[
	A\left(x\right) = 0 + x + \frac{x^2}{2} + \frac{x^3}{3} + ...
\]

Рассмотрим также производящую функцию $B\left(x\right)$ с коэффициентами:
\[
	1, 1, 1, 1, ...
\]

Их композиция, согласно смыслу композиции экспоненциальных производящих функций дает нам решение исходной задачи:
\[
	B\left(A\left(x\right)\right) = exp\left(x + \frac{x^2}{2} + \frac{x^3}{3} + ... \right) = exp\left(ln\left(\frac{1}{1-x}\right)\right)
\]

Таким образом решением является производящая функция $\frac{1}{1 - x}$, но эта производящая функция представляет следующий степенной ряд:
\[
	\frac{1}{1 - x} = \sum_{i=0}^{\infty} x^i = \sum_{i=0}^{\infty}i!\frac{x^i}{i!}
\]

т. е. получили производящую функцию для числа всех перестановок. Можно получить этот результат и другим способом. Число всех перестановок из $n$ элементов $n!$, каждая перестановка может быть пресдтавлена в произведение независимых циклов, например, $\left(1 3 5\right)\left(2 4\right)\left(6\right)$, а это очевидно разбиение $n$-множества на блоки и циклическое упорядочение каждого из них.

\section{Числа Стирлинга первого рода}

Расссмотрим производящую функцию $B\left(x\right)$ с коэффициентами:
\[
	1, t, t^2, t^3, ...
\]

Тогда композиция функций $B\left(A\left(x\right)\right)$ (где $A\left(x\right)$ таже что и раньше) будет представляться как:
\[
	\hat c\left(x,t\right) = \sum_{n=0}^{\infty}\left(\sum_{k=0}^n c\left(n,k\right) t^k\right) \frac{x^n}{n!}
\]
где коэффициенты $c\left(n,k\right)$ - количество разбиений $n$-элементного множества ровно на $k$ циклов. Эти числа называются числами Стирлинга первого рода (часто обозначаются как $\left[n \atop k\right]$).

Очевидно, что производящая функция для них в свернутом виде представляется как:
\[
	\hat c\left(x,t\right) = exp\left(t\cdot ln\left(\frac{1}{1-x}\right)\right) = \frac{1}{\left(1-x\right)^t}
\]